package binaryTree;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

import utils.binaryTreeUtil;
import utils.binaryTreeUtil.TreeNode;

public class levelOrder {
    // 使用队列
    // 不能根据节点的数目来计算层数。除非是完全二叉树，而本题显然不是
    // public static List<List<Integer>> levelOrder(TreeNode root) {
    // //先层序遍历，把结果保存到list当中，最后遍历list
    // Queue<TreeNode> queue =new ArrayDeque<>();
    // ArrayList<Integer> totalList = new ArrayList();
    // List<List<Integer>> list = new ArrayList<>();
    // if (root==null) {
    // return list;
    // }
    // queue.add(root);
    // totalList.add(root.val);
    // while (!queue.isEmpty()) {
    // TreeNode node = queue.poll();

    // if (node.left!=null) {
    // queue.add(node.left);
    // totalList.add(node.left.val);
    // }else{
    // totalList.add(null);
    // }
    // if (node.right!=null) {
    // queue.add(node.right);
    // totalList.add(node.right.val);
    // }else{
    // totalList.add(null);
    // }
    // }
    // //遍历totallist
    // //计算最大层数
    // int depth=(int) (Math.floor(Math.log(totalList.size()) / Math.log(2)) + 1);
    // int start=0,times=0;
    // for(int i=0;i<depth;i++){
    // ArrayList<Integer> subList = new ArrayList();
    // times = (int) Math.pow(2, i);
    // for(int j=0;j<times;j++){
    // Integer val = totalList.get(start+j);
    // if(val!=null){
    // subList.add(val);
    // }
    // }
    // list.add(subList);
    // start+=times;
    // }
    // return list;
    // }
    public static List<List<Integer>> levelOrder(TreeNode root) {
        // 先层序遍历，把结果保存到list当中，最后遍历list
        Queue<TreeNode> queue = new ArrayDeque<>();

        List<List<Integer>> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        queue.add(root);
        while (!queue.isEmpty()) {
            int nums = queue.size();
            ArrayList<Integer> subList = new ArrayList();
            for (int i = 0; i < nums; i++) {
                TreeNode node = queue.poll();
                subList.add(node.val);
                if (node.left!=null) {
                    queue.add(node.left);
                }
                if (node.right!=null) {
                    queue.add(node.right);
                }
            }
            list.add(subList);

        }
        return list;
    }

    public static void main(String[] args) {
        Integer[] inputArray = { 3, 9, 20, null, null, 15, 7 };
        TreeNode root = binaryTreeUtil.buildTree(inputArray);
        List<List<Integer>> levelOrder = levelOrder(root);
        for (List<Integer> sublist : levelOrder) {
            for (Integer num : sublist) {
                System.out.println(num);
            }
            System.out.println("=============");
        }
    }
}
